Graph / Planar graph (Bibtex)

P147: Enumeration of all maximal planar graphs with $n$ vertices

Input:

An integer $n$.

Output:

All maximal planar graph with $n$ vertices.

Complexity:

$O(n^3)$ time per graph with $O(n)$ space.

Comment:

A planar graph with $n$ vertices is \textit{maximal} if it has exactly $3n -6$ edges.

Reference:

[Nakano2004a] (Bibtex)

P155: Enumeration of all based floorplans with at most $n$ faces

Input:

An integer $n$.

Output:

All based floorplans with at most $n$ faces.

Complexity:

$O(1)$ time per solution with $O(n)$ space.

Comment:

A planar graph is called a \textit{floorplan} if every face is a rectangle. A \textit{based floorplan} is a floorplan with one designated base line segment on the outer face.

Reference:

[Nakano2001a] (Bibtex)

P156: Enumeration of all based floorplans with exactly $n$ faces

Input:

An integer $n$.

Output:

All based floorplans with exactly $n$ faces.

Complexity:

$O(1)$ time per solution with $O(n)$ space.

Comment:

A planar graph is called a \textit{floorplan} if every face is a rectangle. A \textit{based floorplan} is a floorplan with one designated base line segment on the outer face.

Reference:

[Nakano2001a] (Bibtex)

P157: Enumeration of all floorplans with exactly $n$ faces

Input:

An integer $n$.

Output:

All floorplans with exactly $n$ faces.

Complexity:

$O(1)$ time per solution with $O(n)$ space.

Comment:

A planar graph is called a \textit{floorplan} if every face is a rectangle.

Reference:

[Nakano2001a] (Bibtex)

P220: Enumeration of all internally triconnected planar graphs

Input:

Integers $n$ and $g$.

Output:

All internally triconnected planar graphs with exactly $n$ vertices such that $\kappa(G) = 2$ and the size of each inner face is at most $g$.

Complexity:

$O(n^3)$ time per solution on average with $O(n)$ space.

Comment:

Reference:

[Zhuang2010a] (Bibtex)